package com.wtgroup.demo.leetcode.q003_重复字符的最长子串;

public class Solution2 {

    /**
     * 无重复字符的最长子串
     *
     * hash 表, 指针跳跃, 消除无用循环
     */

    public static void main(String[] args) {
        // String s = "cdd";
        // int res = new Solution2().lengthOfLongestSubstring(s);
        // System.out.println(res);

        String[] ss = {"", " ", "abcabcbb", "bbbbb", "pwwkew", "au", "cdd", "aab"};
        for (String s : ss) {
            int res = new Solution2().lengthOfLongestSubstring(s);
            System.out.println(res);
        }
        /**
         * 0
         * 1
         * 3
         * 1
         * 3
         * 2
         */
    }

    // public int lengthOfLongestSubstring(String s) {
    //     int maxLen = 0;
    //     int[] tbl = new int[128];
    //     // 初始 hash table , 赋占位值 -1
    //     for (int i = 0; i < tbl.length; i++) {
    //         tbl[i] = -1;
    //     }
    //
    //     int n = s.length();
    //     int i,ri = -1;
    //     int curLen = 0;
    //     for (i = 0; i < n-maxLen; i++) {
    //         char c = 0;
    //         while (++ri < n && tbl[(c = s.charAt(ri))] < i) {
    //             tbl[c] = ri;
    //         }
    //         // here, 重复字符落在当前子串内
    //         i = tbl[c];
    //         tbl[c] = ri;
    //
    //         // 换下一个子串前, 记录当前子串长度
    //         maxLen = Math.max(maxLen, ri - i);
    //     }
    //
    //     return maxLen;
    // }


    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        int[] tbl = new int[128];
        // 初始 hash table , 赋占位值 -1
        for (int i = 0; i < tbl.length; i++) {
            tbl[i] = -1;
        }

        int n = s.length();
        int i,ri = -1;
        for (i = 0; i < n-maxLen; i++) {
            while (++ri < n) {
                char c = s.charAt(ri);
                if (tbl[c] >= i) { // 重复字符落在当前子串内
                    maxLen = Math.max(maxLen, ri - i);
                    i = tbl[c];
                    tbl[c] = ri;
                    break;
                } else {
                    tbl[c] = ri;
                }
            }

            // 考虑一直没有遇到重复字符的情况
            maxLen = Math.max(maxLen, ri - i);
        }

        return maxLen;
    }
}
